package com.veal98.tree;

import com.veal98.bean.TreeNode;

public class LowestCommonAncestorOfABinaryTree_236 {

    public static void main(String[] args) {

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        // p 或者 q 为 root, 那么 root 就是最近公共祖先
        if (root == p || root == q) {
            return root;
        }

        // 左子树上找公共祖先
        TreeNode leftAncestor = lowestCommonAncestor(root.left, p, q);
        // 右子树上找公共祖先
        TreeNode rightAncestor = lowestCommonAncestor(root.right, p, q);

        // 左子树中没有找到公共祖先，那么一定在右子树中
        if (leftAncestor == null) {
            return rightAncestor;
        }
        // 右子树中没有找到公共祖先，那么一定在左子树中
        if (rightAncestor == null) {
            return leftAncestor;
        }

        // 左右子树都没有找到公众祖先，那么 root 就是最近公共祖先
        return root;
    }

}
